package com.tree;

/**
 * 第二次优化:
 * 由于从孩子指向父节点,在 find() 操作时,可能会持续多次 unionArr[unionArr[unionArr[unionArr[...........]]]]
 * 导致整个树的高度很高,不利于层层寻找父节点,因此本次优化,使得在连接时尽量让整个树的高度减少
 */
public class UnionFindImpl_3 extends UnionFindImpl_2 implements IUnionFind {
    private int[] size; //size[k] 表示以 k 为根的集合中元素的个数


    @Override
    public void union(int p, int q) {
        //通过比较 size[] ,就可以将元素少的根,连接到元素多的根上,尽可能减少根的高度
        int pRoot = find(p);
        int qRoot = find(q);
        if (size[pRoot] < size[qRoot]) {
            size[pRoot] += size[qRoot];
            super.union(pRoot, qRoot);
        } else {
            size[pRoot] += size[qRoot];
            super.union(qRoot, pRoot);
        }

    }

    public UnionFindImpl_3(int count) {
        super(count);
        size = new int[count];
        //在初始条件下,每个数据都属于不同的组别
        for (int i = 0; i < count; i++) {
            size[i] = 1;
        }
    }


}
